package com.xj.algorithm.leetcode;

import java.util.HashMap;

/**
 * 回旋镖的数量
 */
public class L447_平面中的点距离回旋镖的数量 {

    /**
     * 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
     * <p>
     * 找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
     * <p>
     * 示例:
     * <p>
     * 输入:
     * [[0,0],[1,0],[2,0]]
     * <p>
     * 输出:
     * 2
     * <p>
     * 解释:
     * 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
     */
    public static void main(String[] args) {
        int[][] points = new int[][]{{0, 0}, {1, 0}, {2, 0}};
        System.out.println(numberOfBoomerangs(points));
    }

    //精彩的解法：暴力比较法和hashmap
    public static int numberOfBoomerangs(int[][] points) {
        int N = points.length;
        int res = 0;
        for (int i = 0; i < N; ++i) {
            int[] pivot = points[i];
            HashMap<Integer, Integer> map = new HashMap<>();

            for (int j = 0; j < N; ++j) {
                if (j == i)
                    continue;
                int dis = (int) Math.pow(pivot[0] - points[j][0], 2) + (int) Math.pow(pivot[1] - points[j][1], 2);
                if (!map.containsKey(dis))
                    map.put(dis, 1);
                else
                    map.put(dis, map.get(dis) + 1);
            }

            //点间距离的公式：(n-1)*n
            for (int d : map.keySet()) {
                if (map.get(d) > 1)
                    res += map.get(d) * (map.get(d) - 1);
            }
        }
        return res;
    }

}
